// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssagen

import (
	"container/heap"
	"fmt"

	"cmd/compile/internal/ir"
	"cmd/compile/internal/ssa"
	"cmd/compile/internal/types"
	"cmd/internal/src"
)

// 该文件包含在函数中放置phi节点的算法。
// None
// https:
// 对于大型函数，我们使用Sreedhar和Gao：放置Φ-节点的线性时间算法。
// http:

const smallBlocks = 500

const debugPhi = false

// fwdRefAux将任意ir.Node包装为ssa.Aux，以便与OpFwdref一起使用。
type fwdRefAux struct {
	_ [0]func() // 确保不比较ir.Node是否相等
	N ir.Node
}

func (fwdRefAux) CanBeAnSSAAux() {}

// insertPhis查找函数中phi所在的所有位置
// 必要时，将其插入。
// 使用FwdRef ops查找变量的所有用法，使用s.defvars查找
// 所有定义。
// 插入Phi值，并将所有FWDREF更改为副本
// 具有适当的phi或定义。
// TODO:以某种方式将此部分作为cmd/compile/internal/ssa的一部分？
func (s *state) insertPhis() {
	if len(s.f.Blocks) <= smallBlocks {
		sps := simplePhiState{s: s, f: s.f, defvars: s.defvars}
		sps.insertPhis()
		return
	}
	ps := phiState{s: s, f: s.f, defvars: s.defvars}
	ps.insertPhis()
}

type phiState struct {
	s       *state                   // SSA州
	f       *ssa.Func                // 要处理的功能
	defvars []map[ir.Node]*ssa.Value // 每个块末尾定义的变量

	varnum map[ir.Node]int32 // 变量编号

	// 支配树的性质
	idom  []*ssa.Block // 支配父母
	tree  []domBlock   // 支配子+兄弟姐妹
	level []int32      // 控制树中的级别（0=根或不可访问，1=根的子级，…）

	// 划痕位置
	priq   blockHeap    // 块的优先级队列，更高级别（朝向叶）=更高优先级
	q      []*ssa.Block // 内环队列
	queued *sparseSet   // 已经放在q里了
	hasPhi *sparseSet   // 他有一个phi
	hasDef *sparseSet   // 写入了我们正在处理的变量

	// 混杂的
	placeholder *ssa.Value // 值用作“尚未设置”占位符。
}

func (s *phiState) insertPhis() {
	if debugPhi {
		fmt.Println(s.f.String())
	}

	// 找到我们需要匹配读写操作的所有变量。
	// 此步骤从考虑中删除任何基本的仅块变量。
	// 为这些变量生成编号。
	s.varnum = map[ir.Node]int32{}
	var vars []ir.Node
	var vartypes []*types.Type
	for _, b := range s.f.Blocks {
		for _, v := range b.Values {
			if v.Op != ssa.OpFwdRef {
				continue
			}
			var_ := v.Aux.(fwdRefAux).N

			// 优化：查看1个块中的定义。
			if len(b.Preds) == 1 {
				c := b.Preds[0].Block()
				if w := s.defvars[c.ID][var_]; w != nil {
					v.Op = ssa.OpCopy
					v.Aux = nil
					v.AddArg(w)
					continue
				}
			}

			if _, ok := s.varnum[var_]; ok {
				continue
			}
			s.varnum[var_] = int32(len(vartypes))
			if debugPhi {
				fmt.Printf("var%d = %v\n", len(vartypes), var_)
			}
			vars = append(vars, var_)
			vartypes = append(vartypes, v.Type)
		}
	}

	if len(vartypes) == 0 {
		return
	}

	// 找到我们需要处理的变量的所有定义。
	// defs[n]包含分配了变量号n的所有块。
	defs := make([][]*ssa.Block, len(vartypes))
	for _, b := range s.f.Blocks {
		for var_ := range s.defvars[b.ID] { // TODO:以其他方式编码DEFVAR（显式操作）？使defvars[n]成为切片而不是贴图。
			if n, ok := s.varnum[var_]; ok {
				defs[n] = append(defs[n], b)
			}
		}
	}

	// 制作支配树。
	s.idom = s.f.Idom()
	s.tree = make([]domBlock, s.f.NumBlocks())
	for _, b := range s.f.Blocks {
		p := s.idom[b.ID]
		if p != nil {
			s.tree[b.ID].sibling = s.tree[p.ID].firstChild
			s.tree[p.ID].firstChild = b
		}
	}
	// 计算支配树中的级别。
	// 使用父指针，我们可以进行深度优先行走，而无需
	// 任何辅助存储器。
	s.level = make([]int32, s.f.NumBlocks())
	b := s.f.Entry
levels:
	for {
		if p := s.idom[b.ID]; p != nil {
			s.level[b.ID] = s.level[p.ID] + 1
			if debugPhi {
				fmt.Printf("level %s = %d\n", b, s.level[b.ID])
			}
		}
		if c := s.tree[b.ID].firstChild; c != nil {
			b = c
			continue
		}
		for {
			if c := s.tree[b.ID].sibling; c != nil {
				b = c
				continue levels
			}
			b = s.idom[b.ID]
			if b == nil {
				break levels
			}
		}
	}

	// 分配临时位置。
	s.priq.level = s.level
	s.q = make([]*ssa.Block, 0, s.f.NumBlocks())
	s.queued = newSparseSet(s.f.NumBlocks())
	s.hasPhi = newSparseSet(s.f.NumBlocks())
	s.hasDef = newSparseSet(s.f.NumBlocks())
	s.placeholder = s.s.entryNewValue0(ssa.OpUnknown, types.TypeInvalid)

	// 为每个变量生成phi ops。
	for n := range vartypes {
		s.insertVarPhis(n, vars[n], defs[n], vartypes[n])
	}

	// 将FwdRefs解析为正确的写入或phi。
	s.resolveFwdRefs()

	// 擦除phi ops的生长素字段中存储的变量号。他们不再需要了。
	for _, b := range s.f.Blocks {
		for _, v := range b.Values {
			if v.Op == ssa.OpPhi {
				v.AuxInt = 0
			}
			// 任何剩余的FWDREF都是死代码。
			if v.Op == ssa.OpFwdRef {
				v.Op = ssa.OpUnknown
				v.Aux = nil
			}
		}
	}
}

func (s *phiState) insertVarPhis(n int, var_ ir.Node, defs []*ssa.Block, typ *types.Type) {
	priq := &s.priq
	q := s.q
	queued := s.queued
	queued.clear()
	hasPhi := s.hasPhi
	hasPhi.clear()
	hasDef := s.hasDef
	hasDef.clear()

	// 将定义块添加到优先级队列。
	for _, b := range defs {
		priq.a = append(priq.a, b)
		hasDef.add(b.ID)
		if debugPhi {
			fmt.Printf("def of var%d in %s\n", n, b)
		}
	}
	heap.Init(priq)

	// 访问定义变量n的区块，从最深到最浅。
	for len(priq.a) > 0 {
		currentRoot := heap.Pop(priq).(*ssa.Block)
		if debugPhi {
			fmt.Printf("currentRoot %s\n", currentRoot)
		}
		// 在定义下面行走子树。
		// 跳过我们在以前的迭代中所做的子树。
		// 找到由定义支配的树的边（支配边界）。
		// 在目标区块插入潜在危险装置。
		if queued.contains(currentRoot.ID) {
			s.s.Fatalf("root already in queue")
		}
		q = append(q, currentRoot)
		queued.add(currentRoot.ID)
		for len(q) > 0 {
			b := q[len(q)-1]
			q = q[:len(q)-1]
			if debugPhi {
				fmt.Printf("  processing %s\n", b)
			}

			currentRootLevel := s.level[currentRoot.ID]
			for _, e := range b.Succs {
				c := e.Block()
				// TODO:如果变量在c处无效，则跳过它。
				if s.level[c.ID] > currentRootLevel {
					// D边，或目标位于currentRoot子树中的边。
					continue
				}
				if hasPhi.contains(c.ID) {
					continue
				}
				// 为变量n向块c添加一个φ。
				hasPhi.add(c.ID)
				v := c.NewValue0I(currentRoot.Pos, ssa.OpPhi, typ, int64(n)) // TODO:线路号对吗？
				// 注意：我们将变量编号存储在phi的生长素字段中。临时由phi大楼使用。
				if var_.Op() == ir.ONAME {
					s.s.addNamedValue(var_.(*ir.Name), v)
				}
				for range c.Preds {
					v.AddArg(s.placeholder) // 实际参数将由resolveFwdRefs填写。
				}
				if debugPhi {
					fmt.Printf("new phi for var%d in %s: %s\n", n, c, v)
				}
				if !hasDef.contains(c.ID) {
					// 现在c区有了这个变量的新定义。
					// 将其添加到要浏览的优先级队列中。
					heap.Push(priq, c)
					hasDef.add(c.ID)
				}
			}

			// 如果孩子们还没有被探望，就去探望他们。
			for c := s.tree[b.ID].firstChild; c != nil; c = s.tree[c.ID].sibling {
				if !queued.contains(c.ID) {
					q = append(q, c)
					queued.add(c.ID)
				}
			}
		}
	}
}

// resolveFwdRefs将所有FwdRef使用链接到其最近的主要定义。
func (s *phiState) resolveFwdRefs() {
	// 对支配树进行深度优先行走，保持跟踪
	// 每个变量最近看到的值的。

	// 从变量ID映射到行走当前点的SSA值。
	values := make([]*ssa.Value, len(s.varnum))
	for i := range values {
		values[i] = s.placeholder
	}

	// 有一大堆工作要做。
	type stackEntry struct {
		b *ssa.Block // 块探索

		// 退出时要恢复的变量/值对
		n int32 // 变量ID
		v *ssa.Value

		// 注：仅设置b或n、v中的一个。
	}
	var stk []stackEntry

	stk = append(stk, stackEntry{b: s.f.Entry})
	for len(stk) > 0 {
		work := stk[len(stk)-1]
		stk = stk[:len(stk)-1]

		b := work.b
		if b == nil {
			// 从块中退出时，这种情况将撤消以下所做的任何分配。
			values[work.n] = work.v
			continue
		}

		// 将PHI处理为新的DEF。他们在这个街区走在前头。
		for _, v := range b.Values {
			if v.Op != ssa.OpPhi {
				continue
			}
			n := int32(v.AuxInt)
			// 记住旧的赋值，这样我们可以在退出b时撤消它。
			stk = append(stk, stackEntry{n: n, v: values[n]})
			// 记录新的作业。
			values[n] = v
		}

		// 将FwdRef op替换为其变量的当前输入值。
		for _, v := range b.Values {
			if v.Op != ssa.OpFwdRef {
				continue
			}
			n := s.varnum[v.Aux.(fwdRefAux).N]
			v.Op = ssa.OpCopy
			v.Aux = nil
			v.AddArg(values[n])
		}

		// 为b中定义的变量建立值。
		for var_, v := range s.defvars[b.ID] {
			n, ok := s.varnum[var_]
			if !ok {
				// 某些变量不能跨越基本块边界。
				continue
			}
			// 记住旧的赋值，这样我们可以在退出b时撤消它。
			stk = append(stk, stackEntry{n: n, v: values[n]})
			// 记录新的作业。
			values[n] = v
		}

		// 用当前输入值替换后续的phi参数。
		for _, e := range b.Succs {
			c, i := e.Block(), e.Index()
			for j := len(c.Values) - 1; j >= 0; j-- {
				v := c.Values[j]
				if v.Op != ssa.OpPhi {
					break // 在phi建设期间，所有phi将位于街区的尽头。
				}
				// 仅设置已解析的参数。
				// 对于非常宽的CFG，这显著加快了phi分辨率。
				// 见golang.org/issue/8225。
				if w := values[v.AuxInt]; w.Op != ssa.OpUnknown {
					v.SetArg(i, w)
				}
			}
		}

		// 让孩子们在支配树上散步。
		for c := s.tree[b.ID].firstChild; c != nil; c = s.tree[c.ID].sibling {
			stk = append(stk, stackEntry{b: c})
		}
	}
}

// domBlock包含额外的每个块信息，用于记录支配树。
type domBlock struct {
	firstChild *ssa.Block // 控制树中块的第一个子元素
	sibling    *ssa.Block // 支配树中父级的下一个子级
}

// 块堆用作优先级队列来实现PiggyBank
// 来自Sreedhar和Gao。那张纸用的是一个更好的数组
// 渐近但在常见情况下更糟
// 保存一组稀疏的块。
type blockHeap struct {
	a     []*ssa.Block // 堆中的块ID
	level []int32      // 支配树中的深度（静态，用于确定优先级）
}

func (h *blockHeap) Len() int      { return len(h.a) }
func (h *blockHeap) Swap(i, j int) { a := h.a; a[i], a[j] = a[j], a[i] }

func (h *blockHeap) Push(x interface{}) {
	v := x.(*ssa.Block)
	h.a = append(h.a, v)
}
func (h *blockHeap) Pop() interface{} {
	old := h.a
	n := len(old)
	x := old[n-1]
	h.a = old[:n-1]
	return x
}
func (h *blockHeap) Less(i, j int) bool {
	return h.level[h.a[i].ID] > h.level[h.a[j].ID]
}

// 待办事项：当需要时，停止行走迭代的自治边界
// 变量是死的。也许可以通过检查
// 我们所在的节点被所有的读取控制着？
// 反向由所有读取中最高的公共继承者控制？

// ../ssa/sparseset.go的副本
// TODO:将此文件移动到../ssa，然后在那里使用sparseSet。
type sparseSet struct {
	dense  []ssa.ID
	sparse []int32
}

// newSparseSet返回一个可以表示
// 介于0和n-1之间的整数
func newSparseSet(n int) *sparseSet {
	return &sparseSet{dense: nil, sparse: make([]int32, n)}
}

func (s *sparseSet) contains(x ssa.ID) bool {
	i := s.sparse[x]
	return i < int32(len(s.dense)) && s.dense[i] == x
}

func (s *sparseSet) add(x ssa.ID) {
	i := s.sparse[x]
	if i < int32(len(s.dense)) && s.dense[i] == x {
		return
	}
	s.dense = append(s.dense, x)
	s.sparse[x] = int32(len(s.dense)) - 1
}

func (s *sparseSet) clear() {
	s.dense = s.dense[:0]
}

// 用于小功能的变体。
type simplePhiState struct {
	s         *state                   // SSA州
	f         *ssa.Func                // 要处理的功能
	fwdrefs   []*ssa.Value             // 待处理的FWDREF列表
	defvars   []map[ir.Node]*ssa.Value // 每个块末尾定义的变量
	reachable []bool                   // 哪些街区可以到达
}

func (s *simplePhiState) insertPhis() {
	s.reachable = ssa.ReachableBlocks(s.f)

	// 查找FwdRef ops。
	for _, b := range s.f.Blocks {
		for _, v := range b.Values {
			if v.Op != ssa.OpFwdRef {
				continue
			}
			s.fwdrefs = append(s.fwdrefs, v)
			var_ := v.Aux.(fwdRefAux).N
			if _, ok := s.defvars[b.ID][var_]; !ok {
				s.defvars[b.ID][var_] = v // 将FwdDefs视为定义。
			}
		}
	}

	var args []*ssa.Value

loop:
	for len(s.fwdrefs) > 0 {
		v := s.fwdrefs[len(s.fwdrefs)-1]
		s.fwdrefs = s.fwdrefs[:len(s.fwdrefs)-1]
		b := v.Block
		var_ := v.Aux.(fwdRefAux).N
		if b == s.f.Entry {
			// 输入时不应存在任何变量。
			s.s.Fatalf("Value live at entry. It shouldn't be. func %s, node %v, value %v", s.f.Name, var_, v)
		}
		if !s.reachable[b.ID] {
			// 这个街区死了。
			// 我们在这里使用什么并不重要，只要格式正确。
			v.Op = ssa.OpUnknown
			v.Aux = nil
			continue
		}
		// 在每个前置项上查找变量值。
		args = args[:0]
		for _, e := range b.Preds {
			args = append(args, s.lookupVarOutgoing(e.Block(), v.Type, var_, v.Pos))
		}

		// 决定我们是否需要phi。如果有，我们需要一个phi
		// 是两个不同的参数（都不是v）。
		var w *ssa.Value
		for _, a := range args {
			if a == v {
				continue // 自我参照
			}
			if a == w {
				continue // 已经有这个证人了
			}
			if w != nil {
				// 两个证人，需要一个phi值
				v.Op = ssa.OpPhi
				v.AddArgs(args...)
				v.Aux = nil
				continue loop
			}
			w = a // 拯救证人
		}
		if w == nil {
			s.s.Fatalf("no witness for reachable phi %s", v)
		}
		// 一名证人。制作一份w。
		v.Op = ssa.OpCopy
		v.Aux = nil
		v.AddArg(w)
	}
}

// lookupVarOutgoing在块b的末尾查找变量的值。
func (s *simplePhiState) lookupVarOutgoing(b *ssa.Block, t *types.Type, var_ ir.Node, line src.XPos) *ssa.Value {
	for {
		if v := s.defvars[b.ID][var_]; v != nil {
			return v
		}
		// 这个变量不是由b定义的，我们还没有找到它。
		// 如果b正好有一个前置项，则循环在那里查找它。
		// 否则，请放弃并插入新的FwdRef，稍后再解决。
		if len(b.Preds) != 1 {
			break
		}
		b = b.Preds[0].Block()
		if !s.reachable[b.ID] {
			// 这是罕见的；它发生在死代码中奇怪的交错无限循环中。
			// 见第19783期。
			break
		}
	}
	// 为变量生成FwdRef并返回该值。
	v := b.NewValue0A(line, ssa.OpFwdRef, t, fwdRefAux{N: var_})
	s.defvars[b.ID][var_] = v
	if var_.Op() == ir.ONAME {
		s.s.addNamedValue(var_.(*ir.Name), v)
	}
	s.fwdrefs = append(s.fwdrefs, v)
	return v
}
